#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int n = mat.size(), m = mat[0].size(), minsum = 0;
        vector<bool> dp(target * 2, false);
        int mintmp = 70;
        for (int j = 0; j < m; j++) {
            if (mat[0][j] < 2 * target) dp[mat[0][j]] = true;
            mintmp = min(mat[0][j], mintmp);
        }
        minsum += mintmp;
        for (int i = 1; i < n; i++) {
            vector<bool> tmp(target * 2, false);
            int tmpm = 70;
            for (int j = 0; j < m; j++) {
                int num = mat[i][j];
                tmpm = min(tmpm, num);
                for (int k = 1; k < 2 * target; k++) {
                    if (dp[k]) {
                        if (k + num < 2 * target) tmp[k + num] = true;
                    }
                }
            }
            minsum += tmpm;
            dp = tmp;
        }
        int ret = INT_MAX;
        //for(int i = 0; i <= target; i++) cout << dp[i] << ' ';
        for (int i = 2 * target - 1; i >= 0; i--) if (dp[i]) ret = min(ret, abs(i - target));
        return min(ret, abs(minsum - target));
    }
};